package primary.code12_dp;

import lombok.extern.slf4j.Slf4j;

/**
 * 不同面值的钞票，可以取无限制张，目标凑够aim元，有几种凑法
 */
@Slf4j
public class Code06_Aim {
    public static int aim1(int[] arr, int index, int rest) {
        if (rest == 0) {
            return 1;
        }
        if (index == arr.length) {
            return 0;
        }
        int count = rest / arr[index];
        int res = 0;
        for (int i = 0; i <= count; i++) {
            res += aim1(arr, index + 1, rest - arr[index] * i);
        }
        return res;
    }


    public static int aim2(int[] arr, int index, int rest) {
        int n = arr.length;
        int[][] dp = new int[n + 1][rest + 1];
        for (int y = 0; y < rest + 1; y++) {
            dp[n][y] = 0;
        }
        for (int x = 0; x < n + 1; x++) {
            dp[x][0] = 1;
        }
        for (int x = n - 1; x >= 0; x--) {
            for (int y = 1; y < rest + 1; y++) {
                int count = y / arr[x];
                int res = 0;
                for (int i = 0; i <= count; i++) {
                    res += dp[x + 1][y - arr[x] * i];
                }
                dp[x][y] = res;
            }
        }
        return dp[index][rest];
    }

    public static int aim3(int[] arr, int index, int rest) {
        int n = arr.length;
        int[][] dp = new int[n + 1][rest + 1];
        for (int y = 0; y < rest + 1; y++) {
            dp[n][y] = 0;
        }
        for (int x = 0; x < n + 1; x++) {
            dp[x][0] = 1;
        }
        for (int x = n - 1; x >= 0; x--) {
            for (int y = 1; y < rest + 1; y++) {
                dp[x][y] = dp[x + 1][y];
                if (y - arr[x] >= 0) {
                    dp[x][y] += dp[x][y - arr[x]];
                }
            }
        }
        return dp[index][rest];
    }

    public static void main(String[] args) {
        int[] arr = {54, 12, 5, 67, 23, 21, 15, 7, 8, 43};
        log.info("暴力递归计算结果：{}", aim1(arr, 0, 100)); // 暴力递归计算结果：586
        log.info("DP计算结果：{}", aim2(arr, 0, 100)); // DP计算结果：586
        log.info("优化DP计算结果：{}", aim3(arr, 0, 100)); // 优化DP计算结果：586
    }
}
